package xiaomin.demo.algorithm;
/*
给定 一个 无序 整型 数组， 找出 第一个 不在 数组 里 的 正 整数。 要求 时间 复杂度 O（ n）， 空间 复杂度 为 O（ 1）。

输入 数组{ 5, 3,- 1, 1}， 返回 2。

 */
public class Lesson18 {
    public static void run(){
        int[] arr={1,-9,3,4,5,7,8,2};

        int start=0;
        int end=arr.length-1;
        int index=0;
        for(int i=0;i<end;i++){
            if(arr[i]<=0 || arr[i]>arr.length){
                arr[i]=0;
            }
            else if(arr[i]!=i+1){
                //交换
                int tmp= arr[arr[i]-1];
                arr[arr[i]-1]=arr[i];
                arr[i]=tmp;
                i--;
            }
        }

        for(int i=0;i<end;i++){
            if(arr[start]>0){
                if(arr[i]!=i+1){
                    index=i+1;
                    break;
                }
            }
        }


//        while (start<end){
//            index=getIndex(arr,start,end);
//            if(arr[index]>index+1){
//                if(index==0) {
//                    break;
//                }
//                else {
//                    if(arr[index-1]==index){
//                        start=index;
//                        break;
//                    }
//                    else if(arr[index-1]>index) {
//                        end=index-1;
//                    }
//                }
//            }
//            else if(arr[index]==index+1) {
//                start=index+1;
//            }
//            else {
//                //如果出现小于，则说明有重复数字
//            }
//        }

        System.out.println(index);
    }

    public static int getIndex(int[] arr,int start,int end){
        //第一个数字
        int tmp=arr[start];
        //双向区间扫描
        while (start<end){
            //先从end扫描
            while (start<end && arr[end]>=tmp){
                end--;
            }
            //遇到小的,填坑到左边
            arr[start]=arr[end];
            //从start扫描
            while(start<end && arr[start]<=tmp){
                start++;
            }
            //遇到大的,填坑到右边
            arr[end]=arr[start];
        }

        arr[start]=tmp;

        return start;
    }
}
